{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Graph\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Xem thêm về [Graph](https://www.tutorialspoint.com/python/python_graphs.htm)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Graph](https://lh3.googleusercontent.com/TyJ1l0k14TSL70z1MsiCbotY0gITfhBkq0prc8jGNqetrLwb_-10i3FjRFXhewGahndp8bTlJKE35spfJ_5rNKWlS6Zy3uEjiMgZrbsai69nGUtdj2eaTpZUMm7fUjSG4vy-2O9Vpwch2iGpjyRxAmebKFGbdAMWaWtH78AuXUBb9pvW9tcH2A7yy208PeaGxVejUdmD-3xEReXfer8TOBC9TaD3yzEupHaI6ioh50ZedK0ZBBsenIl-gMvjWY4ImYP27cJbKL0xCDQDhnTF88__1x8PP8sTuyCGs-XOXz9RdbRTR_AfSbo4kXJN-4F8a61DxNm0CvehNpz7af0ATjYcZr_gA8JwjtVD6C3xS6epU9szyuC9lAFVGBNfYg7SDEeFNKY9_521Kx4hn_DtxoUnltQTTnHzMwr1xUwi9wNfW9dYggVD-cTZtlHKWvFP6mXaRfrpOQQv_F3Qn5bvLgQ8bbYXm0dyQDgM5gEtSOKFBDIXbth6mQspPQcU8975s7c_cUxE_ryjUpiEkf2ttFU0VK9nd3Saq-y9yjq-pauPveze78e8jS-HoUYSbtYuI4ALdeJU7AXWHd_Zlb362SrObaGB7lnj4x88rNLiJR-vVMEsj3SQJTCEgjOfA3f8Fulm-US_goquWaBkXCJy0To8qhg82OS0Fw=w301-h174-no)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Mục đích của Graph là thể hiện mối quan hệ giữa các đối tượng với nhau.\n",
    "    - Đối tượng hình tròn được gọi là các các đỉnh (Node)\n",
    "    - Những đường nối với các Node được gọi là các cạnh (Edge)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### I. Ví dụ về Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 1. Ví dụ 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Bạn có thể tượng tượng Graph giống như các mối quan hệ cuộc sống trong hiện tại của chúng ta."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Graph](https://lh3.googleusercontent.com/yG7r9KfYznzTILAbWVY_mr7N2rxX-TwCEuwlRpjg9Qv4U0kHMaKX73zmWYQ96eIye0dPevM4e6-dF1knF8KrmabwTdsvEKEd3EuNOBP9IXY6FaCxuAIQIlnvoksESeNCSLPZtFlpjP0zTFFM_8MDPVmVCAd-ukCZkJ4vZEp0RXBWFH1Oxcr1c3yS0tYlTUG2UcD_MhFvLw-sg8ykfR_SMG0u2NS21AFiIIi5Xq5IdMoZnD9wDWkXpJSVZKjhDD7EeEdJVddnUjVCQpQ8UNkMGBbfN0Ag2bMiR6YtKi-55if_eot6_h1LtQcr22Ij1fAWnvSosYC2GYnsxig15l0Oz7ACAog9dCmRxZXEdwdDSPP8c3qWSnEKnnbP74hiIx-RKC0I16vmsKW2AXzolR7euV1bb_uqfRtFK8jcdvIhduc0UlqOLw7C9lA4sY5QW99RSqR7dvmpn2eMTV-OywIxP3SAlgkL-S1730kyvdfVvBs8WKMfgmfBP6kmCQli0ier2_5ixgaCyT1FNkN6Os5TQoGN7UYsLrEBDFfPUPIA9m8fgdVi7EhFtQox8vaIgDcNDMDVln-GTXe0nYkHasEhzljyuBnUQEtfOuYrw1zuqWpe0fn5W-4yvdcd_YB0eEAzpUFnSz1Y32rQLdaQCJJL-8P5JNQ1mAAF-w=w800-h600-no)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Các đỉnh lưu trữ dữ liệu về các cá nhân còn các cạnh lưu trữ mức độ mối quan hệ của các cá nhân đó."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 2. Ví dụ 2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Graph có thể dùng để biển hiện quãng đường đi từ Hà Nội cho tới Thành Phố Hồ Chí Minh"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Location Graph](https://lh3.googleusercontent.com/KmlKk5YbpRoWvBGD4LcX5LI2D1E_EurX2nGWd-_Ti6yy7Ylr6-J8othCEVKKcjG-BBl6OpBITQCtWroXEYbxDN3QGQD0Zf4WLxO6rGsaXChX0XTmggayKPQHZaJcqnUyo_O4DEI6wlgLzGP2F-f33Rbp0O9wjCBVZmU-lFWL2FswDib9bnL7two24Veq97l21qdaUW4-UirLKwQZ0hi53vhSK8KLG3Wwk9hvIp2jcknhLVdS93HSm2imahhkkjI623vW77quQT4atWzQUk3VBgQUynZqnGTaS6vJTfJqSCrSDs-r27ALcgM1nehF0B7QCuadq80udrhWJ8wVvwk2zWVTY0RJtv6QfHGGtIfMJ7pKlaAkTVmu7Qj2sam5SW4sdL2-Ds2uB7fU9-K7ZcmMO85RcT7AoIpkPCiaqZmZ-5KB4k85KiTEZCkVlBKfFBGOrb1iv53NGH1XiRRvIl-N1TRRiJkoufu_EpYwuIFA9gPujJ2Ol0e25lfJpnTTCRVCotXHvrOyZeW69Qt7lYECVL19B_cjpnwMatJHZJOoa_3khmM1P0V4eCACTjatjFebWHGRkbKmJYjgus3HqA2AEcyhtNsH01Q2ccGhJ43uNrwukU3FHw2nPuPkpc65TCwdSJsTyiD9E-n24xJ9BbA2L94-5BECO6r-nA=w800-h400-no)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Các đỉnh đại diện cho các thành phố còn các cạnh lưu trữ khoảng cách giữa các thành phố"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### II. Biểu diễn Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![Edge List](https://lh3.googleusercontent.com/qsy38NSZX5Fy_lTfmMsyMnfX8WniEP0fwgsO5p9rSEbMyABgsB3NmM_8Hg1oZgi085Cag7-2D-8wCwi1rIUXQGwvfq0kM1DL6gHPWsE-fyF9s-d6wOCrQirm_tiAy0x4RS3L9J78vpphTnOJWbR3IZxaYsv3jXw-bvfyeXZJU5katBzsm0OLQmpDW_BXyLX6a0srQndkip1IHTUVfYgmJkb2PzAKwO7xC1j-6bnRo3eSrBGyzqniuiZgJCn9HKYwzZLn-P1sfuPF8R7de1qB9Z0LwRLlOl5SaQKaad-lV7HUCrHsCjsQt-CTKvfHLob6arH8QvCxhlAmiTtfhdoeXE3wRpHGzDAL54R5uD6fR4ykunteJ0IHxOfSxBZIdU_5k0m56uLQ9S3MuxgzmA1rfBvvY3XqZ-nlJiDPkWNv8Go2jUMDwe9MsM2aFH2m10dz468aVyC8iRzw2TNhYgDGY6C5gozB7gXQuiEAz0D0LVqwFAsGAbPg_66wPNI-DkxZ5QjxaeklOtP0E38RERLBbqS9WVfGu38E6pUaM7eamJbx0ypUoXa3L7SzlNnTJ14sS5yQ-agWqIs8UyzSKQI9eT8wwbS-p9J0eHyKvDUcEtnwJG86w8kJo6SbD647KhLwAZ0OFL1V6tainjmDp9-2QC0dm2REUQ1m_g=w800-h400-no)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 1. Edge List\n",
    "    - list tất cả các cạnh"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "# List các cạnh của một Graph\n",
    "# mỗi cạnh là một list bao gồm 2 phần tử đại diện cho 2 đỉnh được cạnh đó kết nối lại\n",
    "# đây còn được gọi là mảng 2 chiều (2D dimension)\n",
    "numbers_graph = [\n",
    "    [1, 4],\n",
    "    [1, 5],\n",
    "    [2, 3],\n",
    "    [2, 4],\n",
    "    [3, 5],\n",
    "    [4, 5]\n",
    "]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2. Object Node\n",
    "    - Object chứa các phần tử là các đỉnh\n",
    "    - Key là đỉnh và value là list các đỉnh mà đỉnh hiện tại nối tới"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers_graph_2 = {\n",
    "    \"1\": [\"4\", \"5\"],\n",
    "    \"2\": [\"3\", \"4\"],\n",
    "    \"3\": [\"2\", \"5\"],\n",
    "    \"4\": [\"1\", \"2\", \"5\"],\n",
    "    \"5\": [\"1\", \"3\", \"4\"]\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### III. Hiển thị các đỉnh của một Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self, graph):\n",
    "        if graph is None:\n",
    "            graph = {}\n",
    "        self.graph = graph\n",
    "    # Trả về list keys của object tương đương các đỉnh của graph\n",
    "    def displayNodes(self):\n",
    "        return self.graph.keys()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph1 = Graph(numbers_graph_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['1', '3', '2', '5', '4']"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph1.displayNodes()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### IV. Hiển thị các cạnh của một Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 416,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self, graph):\n",
    "        if graph is None:\n",
    "            graph = {}\n",
    "        self.graph = graph\n",
    "    def displayEdges(self):\n",
    "        edges = []\n",
    "        nodes = self.graph.keys()\n",
    "        # Lặp qua tất cả các node\n",
    "        for node in nodes:\n",
    "            # to_nodes là các đỉnh mà đỉnh hiện tại trỏ tới\n",
    "            to_nodes = self.graph[node]\n",
    "            for to_node in to_nodes:\n",
    "                # Liệt kê tất cả các cạnh có thể xảy ra\n",
    "                edge = set({ node, to_node })\n",
    "                # Thêm các cạnh duy nhất(unique) vào list\n",
    "                if edge not in edges:\n",
    "                    edges.append(edge)\n",
    "        return edges"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 417,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph2 = Graph(numbers_graph_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 418,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[{'10', '11'},\n",
       " {'1', '4'},\n",
       " {'1', '5'},\n",
       " {'1', '2'},\n",
       " {'2', '3'},\n",
       " {'3', '5'},\n",
       " {'2', '4'},\n",
       " {'4', '5'},\n",
       " {'5', '9'}]"
      ]
     },
     "execution_count": 418,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph2.displayEdges()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### V. Thêm một đỉnh vào Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 419,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self, graph):\n",
    "        if graph is None:\n",
    "            graph = {}\n",
    "        self.graph = graph\n",
    "    def displayNodes(self):\n",
    "        return self.graph.keys()\n",
    "    def addNode(self, node):\n",
    "        nodes = self.graph.keys()\n",
    "        # Chỉ thêm vào node không tồn tại trước trong graph\n",
    "        if node not in nodes:\n",
    "            self.graph[node] = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 420,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph3 = Graph(numbers_graph_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 421,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph3.addNode(\"6\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 422,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['11', '10', '1', '3', '2', '5', '4', '6', '9']"
      ]
     },
     "execution_count": 422,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph3.displayNodes()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 423,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': ['4', '5', '2'],\n",
       " '10': ['11'],\n",
       " '11': ['10'],\n",
       " '2': ['3', '4', '1'],\n",
       " '3': ['2', '5'],\n",
       " '4': ['1', '2', '5'],\n",
       " '5': ['1', '3', '4', '9'],\n",
       " '6': [],\n",
       " '9': ['5']}"
      ]
     },
     "execution_count": 423,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph3.graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### VI. Thêm một cạnh vào Graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 424,
   "metadata": {},
   "outputs": [],
   "source": [
    "numbers_graph_2 = {\n",
    "    \"1\": [\"4\", \"5\"],\n",
    "    \"2\": [\"3\", \"4\"],\n",
    "    \"3\": [\"2\", \"5\"],\n",
    "    \"4\": [\"1\", \"2\", \"5\"],\n",
    "    \"5\": [\"1\", \"3\", \"4\"]\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 425,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Graph:\n",
    "    def __init__(self, graph):\n",
    "        if graph is None:\n",
    "            graph = {}\n",
    "        self.graph = graph\n",
    "    def edges(self):\n",
    "        edges = []\n",
    "        nodes = self.graph.keys()\n",
    "        # Lặp qua tất cả các node\n",
    "        for node in nodes:\n",
    "            # to_nodes là các đỉnh mà đỉnh hiện tại trỏ tới\n",
    "            to_nodes = self.graph[node]\n",
    "            for to_node in to_nodes:\n",
    "                # Liệt kê tất cả các cạnh có thể xảy ra\n",
    "                edge = set({ node, to_node })\n",
    "                # Thêm các cạnh duy nhất(unique) vào list\n",
    "                if edge not in edges:\n",
    "                    edges.append(edge)\n",
    "        return edges\n",
    "    def addEdge(self, edge):\n",
    "        if type(edge) is set:\n",
    "            nodes = self.graph.keys()\n",
    "            # Chỉ thêm edge không tồn tại từ trước\n",
    "            if edge not in self.edges():\n",
    "                (edge_start, edge_end) = tuple(edge)\n",
    "                # Trường hợp 1: Đỉnh đầu và đỉnh cuối đều tồn tại\n",
    "                if edge_start in nodes and edge_end in nodes:\n",
    "                    self.graph[edge_start].append(edge_end)\n",
    "                    self.graph[edge_end].append(edge_start)\n",
    "                # Trường hợp 2: Đỉnh đầu tồn tại và đỉnh cuối không tồn tại\n",
    "                elif edge_start in nodes and edge_end not in nodes:\n",
    "                    self.graph[edge_start].append(edge_end)\n",
    "                    self.graph[edge_end] = [edge_start]\n",
    "                # Trường hợp 3: Đỉnh đầu không tồn tại và đỉnh cuối tồn tại\n",
    "                elif edge_start not in nodes and edge_end in nodes:\n",
    "                    self.graph[edge_start] = [edge_end]\n",
    "                    self.graph[edge_end].append(edge_start)\n",
    "                # Trường hợp 4: Cả 2 đỉnh đều không tồn tại\n",
    "                else:\n",
    "                    self.graph[edge_start] = [edge_end]\n",
    "                    self.graph[edge_end] = [edge_start]\n",
    "            else:\n",
    "                print \"This edge is existed\"\n",
    "        else: \n",
    "            print \"Edge type must be set\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 426,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph_4 = Graph(numbers_graph_2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 427,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': ['4', '5'],\n",
       " '2': ['3', '4'],\n",
       " '3': ['2', '5'],\n",
       " '4': ['1', '2', '5'],\n",
       " '5': ['1', '3', '4']}"
      ]
     },
     "execution_count": 427,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph_4.graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 428,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Thêm một cạnh mà cả 2 đỉnh không tồn tại\n",
    "graph_4.addEdge({'10', '11'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 429,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': ['4', '5'],\n",
       " '10': ['11'],\n",
       " '11': ['10'],\n",
       " '2': ['3', '4'],\n",
       " '3': ['2', '5'],\n",
       " '4': ['1', '2', '5'],\n",
       " '5': ['1', '3', '4']}"
      ]
     },
     "execution_count": 429,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph_4.graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 430,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Thêm một cạnh mà cả 1 trong 2 đỉnh tồn tại\n",
    "graph_4.addEdge({'5', '9'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 431,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': ['4', '5'],\n",
       " '10': ['11'],\n",
       " '11': ['10'],\n",
       " '2': ['3', '4'],\n",
       " '3': ['2', '5'],\n",
       " '4': ['1', '2', '5'],\n",
       " '5': ['1', '3', '4', '9'],\n",
       " '9': ['5']}"
      ]
     },
     "execution_count": 431,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph_4.graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 432,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Thêm một cạnh mà cả 2 đỉnh tồn tại và cạnh đó chưa tồn tại"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 433,
   "metadata": {},
   "outputs": [],
   "source": [
    "graph_4.addEdge({'1', '2'})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 434,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'1': ['4', '5', '2'],\n",
       " '10': ['11'],\n",
       " '11': ['10'],\n",
       " '2': ['3', '4', '1'],\n",
       " '3': ['2', '5'],\n",
       " '4': ['1', '2', '5'],\n",
       " '5': ['1', '3', '4', '9'],\n",
       " '9': ['5']}"
      ]
     },
     "execution_count": 434,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "graph_4.graph"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
